package com.leetcode.no347;

import java.util.*;

public class Solution {
    HashMap<Integer, Integer> map = new HashMap<>();

    public int[] topKFrequent(int[] nums, int k) {

        int[] heap = new int[k];

        for (int n : nums) {
            map.put(n, map.getOrDefault(n, 0) + 1);
        }

        Iterator it = map.keySet().iterator();
        int i = 0;
        while (it.hasNext()) {
            // 先初始化一个大小为k的堆，当堆中元素个数为k时，建立小根堆
            if (i < k) {
                heap[i] = (Integer) it.next();
                i++;
                if (i == k) {
                    for (int j = k / 2 - 1; j >= 0; j--) {
                        heapSort(heap, j);
                    }
                }
            } else {   //小根堆建好后 ，对于每个新遍历的元素与堆顶比较，如果比堆顶大，替换堆顶，重新维持小根堆
                int key = (Integer) it.next();
                if (map.get(key) > map.get(heap[0])) heap[0] = key;
                heapSort(heap, 0);
            }

        }

        return heap;
    }

    //维持小根堆
    //注意，堆中元素比较是比较它们出现的次数，即该元素在map中对应的value
    public void heapSort(int[] heap, int i) {
        int temp = heap[i];
        for (int j = 2 * i + 1; j < heap.length; j = 2 * j + 1) {
            if (j + 1 < heap.length && map.get(heap[j + 1]) < map.get(heap[j])) j++;
            if (map.get(heap[j]) < map.get(temp)) {
                heap[i] = heap[j];
                i = j;
            } else break;
        }
        heap[i] = temp;
    }
}
